﻿/*
#include <math.h>
#include <algorithm>
#include <string>
#include <map>
#include <hash_map>
#include <set>
#include <vector>
#include <iostream>
#include <sstream>
using namespace std;

int partion(string &str,int left,int right){
	int i=left,k=right;
	char x=str[left];
	while(i<k){
		while(i<k&&str[k]>=x)k--;
		str[i]=str[k];
		while(i<k&&str[i]<x)i++;
		str[k]=str[i];
	}
	str[i]=x;
	return i;
}
void quickSort(string &str,int left,int right){
	if(left<right){
		int mid=partion(str,left,right);
		quickSort(str,left,mid-1);
		quickSort(str,mid+1,right);
	}
}
vector<vector<string>> groupAnagrams(vector<string>& strs) {
	vector<vector<string>> re;
	map<string,int> dic;
	vector<string>tmp;
	int len=0;
	for(int i=0;i<strs.size();i++){
		string str=strs[i];
		quickSort(str,0,str.length()-1);
		int index=dic[str];
		if(index==0){
			tmp.clear();
			tmp.push_back(strs[i]);
			re.push_back(tmp);
			len++;
			dic[str]=len;
		}
		else{
			tmp=re[index-1];
			tmp.push_back(strs[i]);
			re[index-1]=tmp;
		}
	}
	for(int i=0;i<re.size();i++){
		sort(re[i].begin(),re[i].end());
	}
	return re;
}

double myPow(double x, int n) {
	if(n==0||n==INT_MIN)
		return 1.0;
	if(n<0)
		return 1.0/myPow(x,-n);
	double half=myPow(x,n>>1);
	if(n%2==0)
		return half*half;
	else
		return half*half*x;
}


//初始化N皇后位置
void initQueueMap(vector<int>&queueLocation,int n){
	for(int i=0;i<n;i++){
		queueLocation.push_back(-1);
	}
}
//获取该行皇后的可选位置
vector<int> getQueueIndexForLine(vector<int>&queueLocation,int lineNumber,int n){
	vector<int> tmp;
	int *seat=new int[n]();
	int index=-1;
	for(int i=0;i<n;i++)
		seat[i]=1;
	for(int i=0;i<lineNumber;i++){
		if(queueLocation[i]!=-1){
			seat[queueLocation[i]]=0;
			index=queueLocation[i]-(lineNumber-i);
			if(index>=0)
				seat[index]=0;
			index=queueLocation[i]+(lineNumber-i);
			if(index<n)
				seat[index]=0;
		}
	}
	for(int i=0;i<n;i++)
		if(seat[i]==1)
			tmp.push_back(i);
	return tmp;
}
bool solveNQueensResult(vector<vector<string>> &result,vector<int>&queueLocation,int lineNumber,int n) {
	vector<int>available=getQueueIndexForLine(queueLocation,lineNumber,n);
	if(available.size()<1)
		return false;
	if(lineNumber==n-1){
		vector<int>loc=queueLocation;
		for(int i=0;i<available.size();i++){
			loc[lineNumber]=available[i];
			vector<string>avilRe;
			for(int k=0;k<n;k++){
				string line="";
				for(int w=0;w<n;w++){
					if(loc[k]==w)
						line+='Q';
					else
						line+='.';
				}
				avilRe.push_back(line);
			}
			result.push_back(avilRe);
		}
		return true;
	}
	for(int i=0;i<available.size();i++){
		queueLocation[lineNumber]=available[i];
		solveNQueensResult(result,queueLocation,lineNumber+1,n);
		queueLocation[lineNumber]=-1;
	}
}
vector<vector<string>> solveNQueens(int n) {
	vector<int>queueLocation;//每个皇后的位置
	initQueueMap(queueLocation,n);
	vector<vector<string>> result;
	solveNQueensResult(result,queueLocation,0,n);
	return result;
}

void solveNQueensResult2(int &result,vector<int>&queueLocation,int lineNumber,int n) {
	vector<int>available=getQueueIndexForLine(queueLocation,lineNumber,n);
	if(available.size()<1)
		return;
	if(lineNumber==n-1){
		result+=available.size();
		return;
	}
	for(int i=0;i<available.size();i++){
		queueLocation[lineNumber]=available[i];
		solveNQueensResult2(result,queueLocation,lineNumber+1,n);
		queueLocation[lineNumber]=-1;
	}
}

int totalNQueens(int n) {
	vector<int>queueLocation;//每个皇后的位置
	initQueueMap(queueLocation,n);
	int result=0;
	solveNQueensResult2(result,queueLocation,0,n);
	return result;
}
int maxSubArray(vector<int>& nums) {
	int re=nums[0],sum=nums[0];
	for(int i=1;i<nums.size();i++){
		if(sum<0)
			sum=0;
		sum+=nums[i];
		if(nums[i]<0)
			continue;
		re=max(re,sum);
	}
	return re;
}
vector<vector<int>>loadBoard(int m,int n){
	vector<vector<int>>board;
	int ch;
	vector<int>row;
	FILE* fp=fopen("sudoku.txt" ,"r");
	for(int k=0;k<m;k++){
		row.clear();
		for(int i=0;i<n;i++){
			fscanf(fp,"%d",&ch);
			row.push_back(ch);
		}
		board.push_back(row);
	}
	return board;
}
vector<int> spiralOrder(vector<vector<int>>& matrix) {
	vector<int> result;
	if(matrix.size()<1)
		return result;
	int m=matrix.size();
	int n=matrix[0].size();
	int loops=min(n/2,m/2);
	int startX,startY,lenRow,lenColumn;
	for(int i=0;i<loops;i++){
		startX=i;startY=i;lenRow=n-2*i;lenColumn=m-2*i;
		//向右
		for(int k=0;k<lenRow;k++)
			result.push_back(matrix[startX][startY+k]);
		//向下
		for(int k=1;k<lenColumn;k++)
			result.push_back(matrix[startX+k][startY+lenRow-1]);
		//向左
		for(int k=lenRow-2;k>=0;k--)
			result.push_back(matrix[startX+lenColumn-1][startY+k]);
		//向上
		for(int k=lenColumn-2;k>=1;k--)
			result.push_back(matrix[startX+k][startY]);
	}
	int minN=min(m,n);
	if(minN%2==1){
		if(m>n){
			for(int i=0;i<m-2*loops;i++)
				result.push_back(matrix[loops+i][loops]);
		}
		else{
			for(int i=0;i<n-2*loops;i++)
				result.push_back(matrix[loops][loops+i]);
		}
	}
	return result;
}
bool canJump(vector<int>& nums) {
	int maxJumped=0;
	for(int i=0;i<nums.size();i++){
		if(i>maxJumped)
			return false;
		if(i+nums[i]>maxJumped){
			maxJumped=i+nums[i];
			if(maxJumped>=nums.size()-1)
				return true;
		}
	}
	return true;
}



struct Interval {
     int start;
     int end;
     Interval() : start(0), end(0) {}
     Interval(int s, int e) : start(s), end(e) {}
 };
int partion(vector<Interval>&intervals,int left,int right){
	int i=left,k=right;
	Interval x=intervals[left],tmp;
	while(i<k){
		while(i<k&&intervals[k].start>=x.start)k--;
		tmp=intervals[i];
		intervals[i]=intervals[k];
		intervals[k]=tmp;
		while(i<k&&intervals[i].start<x.start)i++;
		tmp=intervals[k];
		intervals[k]=intervals[i];
		intervals[i]=tmp;
	}
	intervals[i]=x;
	return i;
}
void quickSort(vector<Interval>& intervals,int left,int right){
	if(left<right){
		int mid=partion(intervals,left,right);
		quickSort(intervals,left,mid-1);
		quickSort(intervals,mid+1,right);
	}
}
vector<Interval> merge(vector<Interval>& intervals) {
	vector<Interval>result;
	if(intervals.size()<1)
		return result;
	quickSort(intervals,0,intervals.size()-1);
	bool flag=true;
	Interval tmp,pre=intervals[0];
	int left=pre.start,right=pre.end;
	for(int i=1;i<intervals.size();i++){
		tmp=intervals[i];
		if(tmp.end<=right){
			continue;
		}
		if(tmp.end>right){
			if(tmp.start>right){
				pre=Interval(left,right);
				result.push_back(pre);
				left=tmp.start;
				right=tmp.end;
			}else{
				right=tmp.end;
			}
		}
	}
	pre=Interval(left,right);
	result.push_back(pre);
	return result;
}
vector<Interval> loadData(int m){
	vector<Interval>board;
	int a,b;
	FILE* fp=fopen("sudoku.txt" ,"r");
	for(int k=0;k<m;k++){
		fscanf(fp,"%d",&a);fscanf(fp,"%d",&b);
		board.push_back(Interval(a,b));
	}
	return board;
}

vector<Interval> insert(vector<Interval>& intervals, Interval newInterval) {
	vector<Interval>result;
	if(intervals.size()<1){
		result.push_back(newInterval);
		return result;
	}
	int left=intervals[0].start,right=intervals[0].end;
	bool flag1=true,flag2=true,tmp;
	for(int i=0;i<intervals.size();i++){
		tmp=true;
		if(flag1){//左边沿未确定区间
			if(newInterval.start<=intervals[i].start){//左边沿确定
				left=newInterval.start;
				flag1=false;
				tmp=false;
			}
			else if(newInterval.start<=intervals[i].end){//左边沿确定
				left=intervals[i].start;
				flag1=false;
				tmp=false;
			}
		}
		if(!flag1&&flag2){//左边沿确定，右边沿未确定区间
			if(newInterval.end<intervals[i].start){//右边沿确定
				right=newInterval.end;
				flag2=false;
				tmp=true;
				result.push_back(Interval(left,right));
			}
			else if(newInterval.end<=intervals[i].end){//右边沿确定
				right=intervals[i].end;
				flag2=false;
				tmp=false;
				result.push_back(Interval(left,right));
			}else{
				tmp=false;
			}
		}
		if(tmp)
			result.push_back(intervals[i]);
	}
	if(!flag1&&flag2){//右边沿未确定，左边沿确定
		result.push_back(Interval(left,newInterval.end));
	}else if(flag1)//左边沿未确定
		result.push_back(Interval(newInterval.start,newInterval.end));
	return result;
}
int lengthOfLastWord(string s) {
	if(s.length()<1)
		return 0;
	int len=0,i=0;
	for(i=s.length()-1;s[i]==' ';i--);
	for(len=0;i>=0&&(s[i]>='a'&&s[i]<='z'||s[i]>='A'&&s[i]<='Z');i--,len++);
	return len;
}
vector<vector<int>> generateMatrix(int n) {
	vector<vector<int>>result;
	for(int i=0;i<n;i++){
		vector<int>row(n);
		result.push_back(row);
	}
	int loop=n/2;
	int startX,startY,len,x=1;
	for(int i=0;i<loop;i++){
		startX=startY=i;
		len=n-2*i;
		//向右
		for(int k=0;k<len;k++)
			result[startX][startY+k]=x++;
		//向下
		for(int k=1;k<len;k++)
			result[startX+k][startY+len-1]=x++;
		//向左
		for(int k=len-2;k>=0;k--)
			result[startX+len-1][startY+k]=x++;
		//向上
		for(int k=len-2;k>=1;k--)
			result[startX+k][startY]=x++;
	}
	if(n%2==1){
		result[loop][loop]=x++;
	}
	return result;
}
string getPermutation(int n, int k) {

}

int main(){
	string p;
	//8,2,4,4,4,9,5,2,5,8,8,0,8,6,9,1,1,6,3,5,1,2,6,6,0,4,8,6,0,3,2,8,7,6,5,1,7,0,3,4,8,3,5,9,0,4,0,1,0,5,9,2,0,7,0,2,1,0,8,2,5,1,2,3,9,7,4,7,0,0,1,8,5,6,7,5,1,9,9,3,5,0,7,5
	int a[]={0};
	vector<int>v1(a,a+sizeof(a)/sizeof(int));
	string b[]={"eat", "tea", "tan", "ate", "nat", "bat"};
	char s1[100],p1[100];
	vector<vector<int>>re= generateMatrix(4);
	cout<<endl;
	system("pause");
	return 0;
}
*/